class Solution(object):
    def numDecodings(self, s):
        n = len(s)
        DP = [0] * n
        base = 10 ** 9 + 7
        for i in range(n):
            if s[i] == '*':
                if i == 0:
                    DP[i] = 9
                else:
                    if s[i - 1] == '1':
                        if i == 1:
                            DP[i] = 9 * DP[i - 1] + 9
                        else:
                            DP[i] = 9 * DP[i - 1] + 9 * DP[i - 2]
                    else:
                        if s[i - 1] == '2':
                            if i == 1:
                                DP[i] = 9 * DP[i - 1] + 6
                            else:
                                DP[i] = 9 * DP[i - 1] + 6 * DP[i - 2]
                        else:
                            if s[i - 1] == '*':
                                if i == 1:
                                    DP[i] = 9 * DP[i - 1] + 15
                                else:
                                    DP[i] = 9 * DP[i - 1] + 15 * DP[i - 2]
                            else:
                                DP[i] = 9 * DP[i - 1]
            else:
                if '1' <= s[i] <= '6':
                    if i == 0:
                        DP[i] = 1
                    else:
                        if s[i - 1] == '1' or s[i - 1] == '2':
                            if i == 1:
                                DP[i] = DP[i - 1] + 1
                            else:
                                DP[i] = DP[i - 1] + DP[i - 2]
                        else:
                            if s[i - 1] == '*':
                                if i == 1:
                                    DP[i] = DP[i - 1] + 2
                                else:
                                    DP[i] = DP[i - 1] + 2 * DP[i - 2]
                            else:
                                DP[i] = DP[i - 1]
                else:
                    if '7' <= s[i] <= '9':
                        if i == 0:
                            DP[i] = 1
                        else:
                            if s[i - 1] == '1' or s[i - 1] == '*':
                                if i == 1:
                                    DP[i] = DP[i - 1] + 1
                                else:
                                    DP[i] = DP[i - 1] + DP[i - 2]
                            else:
                                DP[i] = DP[i - 1]
                    else:
                        if i == 0:
                            DP[i] = 0
                        else:
                            if s[i - 1] == '1' or s[i - 1] == '2':
                                if i == 1:
                                    DP[i] =1
                                else:
                                    DP[i] = DP[i - 2]
                            else:
                                if s[i - 1] == '*':
                                    if i == 1:
                                        DP[i] = 2
                                    else:
                                        DP[i] = 2 * DP[i - 2]
                                else:
                                    DP[i] = 0
            DP[i] %= base
        return DP[-1]
